package site.wanjiahao;

import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        System.out.println(fib1(5));
        System.out.println(fib2(5, 1, 1));
    }

    // 递归100%可以装换为非递归，可以模拟使用栈结果，内部保存局部变量信息
    static void log(int n) {
        if (n < 1) return;
        log(n - 1);
        int v = n + 10;
        System.out.println(v);
    }

    // 模拟栈
    static void log1(int n) {
        Stack<Frame> stack = new Stack<>();
        while (n > 0) {
            stack.push(new Frame(n, n + 10));
            n--;
        }
        // 弹出栈
        while (!stack.isEmpty()) {
            Frame frame = stack.pop();
            System.out.println(frame.v);
        }
    }

    // 斐波那契数列，没有使用尾递归优化
    static int fib1(int n) {
        if (n <= 2) return 1;
        return fib1(n - 1) + fib1(n - 2);
    }

    // 使用尾递归优化
    static int fib2(int n, int first, int second) {
        if (n <= 1) return first;
        return fib2(n - 1, second, first + second);
    }
}
